<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>插入排序与优化 - 算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            min-height: 100vh;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #282c34;
            color: #abb2bf;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-block pre {
            padding: 1.5rem;
            overflow-x: auto;
        }
        .keyword { color: #c678dd; }
        .function { color: #61afef; }
        .string { color: #98c379; }
        .number { color: #d19a66; }
        .comment { color: #5c6370; font-style: italic; }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            color: #667eea;
            font-family: 'Noto Serif SC', serif;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        .complexity-badge {
            background: linear-gradient(135deg, #f093fb 0%, #f5576c 100%);
            color: white;
            padding: 0.5rem 1rem;
            border-radius: 9999px;
            font-weight: 600;
            display: inline-block;
            margin: 0.5rem 0.5rem 0.5rem 0;
        }
        @keyframes fadeInUp {
            from {
                opacity: 0;
                transform: translateY(30px);
            }
            to {
                opacity: 1;
                transform: translateY(0);
            }
        }
        .animate-fadeInUp {
            animation: fadeInUp 0.8s ease-out;
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-6xl mx-auto animate-fadeInUp">
            <div class="text-center">
                <h1 class="text-5xl md:text-6xl font-bold mb-6">
                    <i class="fas fa-sort-amount-up mr-4"></i>插入排序与优化
                </h1>
                <p class="text-xl md:text-2xl opacity-90 max-w-3xl mx-auto">
                    深入理解经典排序算法，探索二分查找优化技巧
                </p>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- 题目描述卡片 -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8 card-hover">
            <div class="flex items-center mb-4">
                <i class="fas fa-tasks text-3xl text-purple-600 mr-4"></i>
                <h2 class="text-3xl font-bold text-gray-800">题目描述</h2>
            </div>
            <p class="text-lg text-gray-700 leading-relaxed">
                <span class="drop-cap">实</span>现插入排序算法，对给定的无序数组进行排序。并尝试通过二分查找等方式优化插入排序的效率。这是一道考察基础排序算法理解和优化能力的经典题目。
            </p>
        </div>

        <!-- 核心考点 -->
        <div class="grid md:grid-cols-2 gap-8 mb-8">
            <div class="bg-gradient-to-br from-purple-50 to-pink-50 rounded-2xl p-8 card-hover">
                <div class="flex items-center mb-4">
                    <i class="fas fa-brain text-3xl text-purple-600 mr-4"></i>
                    <h3 class="text-2xl font-bold text-gray-800">核心考点</h3>
                </div>
                <div class="space-y-3">
                    <div class="flex items-center">
                        <i class="fas fa-check-circle text-green-500 mr-3"></i>
                        <span class="text-lg">插入排序算法实现</span>
                    </div>
                    <div class="flex items-center">
                        <i class="fas fa-check-circle text-green-500 mr-3"></i>
                        <span class="text-lg">算法时间复杂度分析</span>
                    </div>
                    <div class="flex items-center">
                        <i class="fas fa-check-circle text-green-500 mr-3"></i>
                        <span class="text-lg">二分查找优化思路</span>
                    </div>
                </div>
            </div>

            <div class="bg-gradient-to-br from-blue-50 to-indigo-50 rounded-2xl p-8 card-hover">
                <div class="flex items-center mb-4">
                    <i class="fas fa-chart-line text-3xl text-blue-600 mr-4"></i>
                    <h3 class="text-2xl font-bold text-gray-800">复杂度分析</h3>
                </div>
                <div class="space-y-4">
                    <div>
                        <span class="complexity-badge">时间复杂度</span>
                        <p class="text-lg mt-2">O(n²) - 平均和最坏情况</p>
                        <p class="text-lg">O(n) - 最好情况（已排序）</p>
                    </div>
                    <div>
                        <span class="complexity-badge">空间复杂度</span>
                        <p class="text-lg mt-2">O(1) - 原地排序</p>
                    </div>
                </div>
            </div>
        </div>

        <!-- 算法可视化 -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8">
            <h3 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-project-diagram text-purple-600 mr-4"></i>
                算法流程图
            </h3>
            <div class="mermaid">
                graph TD
                    A[开始] --> B[从第二个元素开始遍历]
                    B --> C{是否遍历完成?}
                    C -->|否| D[取出当前元素作为key]
                    D --> E[从已排序部分末尾开始比较]
                    E --> F{key < 当前比较元素?}
                    F -->|是| G[将比较元素后移一位]
                    G --> H[继续向前比较]
                    H --> F
                    F -->|否| I[将key插入当前位置]
                    I --> J[移动到下一个元素]
                    J --> C
                    C -->|是| K[排序完成]
                    
                    style A fill:#667eea,stroke:#fff,stroke-width:2px,color:#fff
                    style K fill:#48bb78,stroke:#fff,stroke-width:2px,color:#fff
                    style D fill:#f6ad55,stroke:#fff,stroke-width:2px,color:#fff
            </div>
        </div>

        <!-- 解题思路 -->
        <div class="bg-gradient-to-r from-gray-50 to-gray-100 rounded-2xl p-8 mb-8">
            <h3 class="text-2xl font-bold text-gray-800 mb-6 flex items-center">
                <i class="fas fa-lightbulb text-yellow-500 mr-4"></i>
                解题思路
            </h3>
            <div class="grid md:grid-cols-2 gap-6">
                <div class="bg-white rounded-xl p-6 shadow-md">
                    <h4 class="text-xl font-semibold text-purple-700 mb-3">
                        <i class="fas fa-code mr-2"></i>基础实现
                    </h4>
                    <ul class="space-y-2 text-gray-700">
                        <li class="flex items-start">
                            <i class="fas fa-arrow-right text-purple-500 mt-1 mr-3"></i>
                            <span>将数组分为已排序和未排序两部分</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-arrow-right text-purple-500 mt-1 mr-3"></i>
                            <span>逐个将未排序元素插入到已排序部分的正确位置</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-arrow-right text-purple-500 mt-1 mr-3"></i>
                            <span>通过比较和移动找到插入位置</span>
                        </li>
                    </ul>
                </div>
                <div class="bg-white rounded-xl p-6 shadow-md">
                    <h4 class="text-xl font-semibold text-blue-700 mb-3">
                        <i class="fas fa-rocket mr-2"></i>优化方案
                    </h4>
                    <ul class="space-y-2 text-gray-700">
                        <li class="flex items-start">
                            <i class="fas fa-arrow-right text-blue-500 mt-1 mr-3"></i>
                            <span>使用二分查找确定插入位置</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-arrow-right text-blue-500 mt-1 mr-3"></i>
                            <span>减少比较次数，从O(n)降至O(log n)</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-arrow-right text-blue-500 mt-1 mr-3"></i>
                            <span>注意：移动操作仍为O(n)，总体复杂度不变</span>
                        </li>
                    </ul>
                </div>
            </div>
        </div>

        <!-- 代码实现 -->
        <div class="bg-white rounded-2xl shadow-xl overflow-hidden mb-8">
            <div class="bg-gradient-to-r from-purple-600 to-pink-600 text-white p-6">
                <h3 class="text-2xl font-bold flex items-center">
                    <i class="fas fa-code mr-4"></i>
                    示例代码
                </h3>
            </div>
            <div class="code-block">
                <pre><code><span class="keyword">def</span> <span class="function">insertionSort</span>(nums):
    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="function">range</span>(<span class="number">1</span>, <span class="function">len</span>(nums)):
        key = nums[i]
        j = i - <span class="number">1</span>
        <span class="keyword">while</span> j >= <span class="number">0</span> <span class="keyword">and</span> nums[j] > key:
            nums[j + <span class="number">1</span>] = nums[j]
            j -= <span class="number">1</span>
        nums[j + <span class="number">1</span>] = key
    <span class="keyword">return</span> nums

<span class="comment"># 二分查找优化版本</span>
<span class="keyword">def</span> <span class="function">binaryInsertionSort</span>(nums):
    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="function">range</span>(<span class="number">1</span>, <span class="function">len</span>(nums)):
        key = nums[i]
        left, right = <span class="number">0</span>, i
        <span class="comment"># 二分查找插入位置</span>
        <span class="keyword">while</span> left < right:
            mid = (left + right) // <span class="number">2</span>
            <span class="keyword">if</span> nums[mid] > key:
                right = mid
            <span class="keyword">else</span>:
                left = mid + <span class="number">1</span>
        <span class="comment"># 移动元素并插入</span>
        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="function">range</span>(i, left, -<span class="number">1</span>):
            nums[j] = nums[j - <span class="number">1</span>]
        nums[left] = key
    <span class="keyword">return</span> nums</code></pre>
            </div>
        </div>

        <!-- 关键概念解释 -->
        <div class="grid md:grid-cols-3 gap-6 mb-8">
            <div class="bg-gradient-to-br from-purple-100 to-purple-200 rounded-xl p-6 card-hover">
                <i class="fas fa-exchange-alt text-4xl text-purple-600 mb-4"></i>
                <h4 class="text-xl font-bold text-gray-800 mb-2">稳定性</h4>
                <p class